Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”

,

где вектор признаков, ,

- весовой вектор, .

Если рассматривать расширенные вектора признаков с дополнительной последней компонентой 1, то указанное соотношение можно представить в виде:

,

где , .

Предполагается, что в случае разбиения на два класса , решающая функция обладает свойствами

Рассмотрим случай разбиения на несколько классов , т.е. предполагается что объекты принадлежат более чем двум классам.

Наиболее общим подходом к решению задачи многоклассового распознавания является метод попарного разделения классов [1 ].

В этом методе каждый класс отделяется от другого, взятого в отдельности, индивидуальной разделяющей поверхностью, т. е. классы предполагаются попарно разделимыми. В этом случае существует разделяющих поверхностей. Решающие функции имеют вид и обладают тем свойством, что если образ принадлежит к классу , то

для всех ;

кроме того, .

Использование полного набора решающих функций , для попарного разделения требует высоких вычислительных затрат.

Метод последовательных дихотомий основан на геометрическом подходе к задаче распознавания. Каждая линейная разделяющая функция , разделяющая множества и , рассматривается как гиперплоскость в пространстве , проходящая между совокупностями точек и . Для каждой гиперплоскости определено положительное и отрицательное направления.

Основная задача построения решающего правила многоклассового распознавания состоит в том, чтобы, используя совокупность гиперплоскостей , , разбить все пространство признаков на области, каждая из которых содержит векторы, соответствующие лишь одному классу объектов. Предполагается возможность существования сложных классов, которым в пространстве признаков соответствует более одного множество. На начальном этапе по некоторому правилу выбирается одна из разделяющих гиперплоскостей . Номера групп, лежащих по положительную сторону от гиперплоскости , заносятся в список положительно полупространства. Номера групп, рассекаемых гиперплоскостью, заносятся в оба списка. На этом начальный этап разделения завершается и производится переход к следующему этапу.

Одним из первых был предложен и реализован критерий ближайших множеств. Суть этого критерия состоит в том, что на каждом -ом шаге классификации из всех множеств выбирается пара ближайших в некотором смысле множеств . Соответствующая этой паре разделяющая гиперплоскость и выбирается на данном шаге.

Если на некотором шаге классификации была выбрана пара множеств и и соответствующая ей гиперплоскость разделила не только пару и , но и еще некоторую пару и , то будем говорить, что произошло попутное разделение пары и . Это явление служит фактором, сокращающим количество используемых разделяющих гиперплоскостей.

Обоснование критерия ближайших множеств состоит в том, что при произвольном взаимном расположении совокупности множеств для пары ближайших множеств минимальна вероятность попутного разделения. Первоочередный выбор ближайших множеств в процессе классификации максимизирует вероятность попутной разделения остальных множеств. Применение критерия ближайших множеств для построения многоклассовой распознающей системы гарантирует получение не худшей по параметру системы среди всех возможных.

Однако более эффективным по параметру является критерий, который условно можно назвать критерием максимального разделения. Для его определения введем переменную, зависящую от числа положительных множеств и отрицательных множеств относительно гиперплоскости в анализируемой области

.

На каждом этапе разделения анализируются только множества, входящие в рассматриваемую область. С учетом этих множеств вычисляются значения и для разных гиперплоскостей. Выбирается та гиперплоскость, которой соответствует максимальное значение переменной . Для реализации алгоритма построения последовательного решающего правила с критерием максимального разделения удобно пользоваться структурной матрицей . В каждой -й строке матрицы , соответствующей разделяющей гиперплоскости , число единиц и число нулей равно величинам и , соответственно.

Эффективность критерия максимального разделения по параметру определяется тем, что набор разделяющих функций, включаемых в решающее правило равен набору, получаемому с помощью алгоритма поиска кратчайшего покрытия [2]. Действительно, если в этом алгоритме на каждом шаге выбиралась строка матрицы , содержащая максимальное количество единиц, то значение переменной , вычисляемое для строки матрицы , как раз равно числу единиц в соответствующей строке матрицы .

Для данного примера можно получить эффективное решение основанное на критерии максимального разделения с использованием процедуры минимизации структурной матрицы . Результат построения дерева решения приведен на рис. 2. При этом использовано всего 4 разделяющих функции.

Таким образом, применение деревьев решений в задачах многоклассового распознавания позволяет существенно уменьшить вычислительные затрат принятия общего решения.

1. Ту Дж., Гонсалес Р. Принципы распознавания образов.-М.: Мир,1978.
2. Закревский А.Д. Алгоритмы синтеза дискретных автоматов.-М.: Наука,1971.